package com.kaizen.leet538;

/**
 * 538. 把二叉搜索树转换为累加树
 *
 */
class SolutionKaizen {

    /**
     * [5,2,13]
     * @param args
     */
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(13);
        convertBST(treeNode);
    }
    private static int num = 0;
    /**
     * 二叉搜索数
     * 左<根<右
     * 思路如下：
     * 递归是最后的节点先开始算
     * 把节点右边的值都加给这个节点
     * 自顶向下遍历并更新值
     * @param root
     * @return
     */
    public static TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            num += root.val;
            root.val = num;
            convertBST(root.left);
        }
        return root;
    }




    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}